package leetcode;

/**
 * 题目：将有序数组转换为二叉搜索树
 * 链接：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/
 */
public class SortedArrayToBST {
    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
    }
    public static void main(String[] args) {
        int[] arr = {-10, -3, 0, 5, 9};
        TreeNode root = sortedArrayToBST(arr);
        inOrderTraversal(root);
    }
    public static TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }
    public static TreeNode dfs(int[] nums, int lo, int hi) {
        if(lo > hi) return null;
        // 计算mid中值
        int mid = lo + (hi - lo) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = dfs(nums, lo, mid - 1);
        root.right = dfs(nums, mid + 1, hi);
        return root;
    }

    // 中序遍历验证树结构（左-根-右）
    public static void inOrderTraversal(TreeNode root) {
        inOrderRecursive(root);
    }

    private static void inOrderRecursive(TreeNode root) {
        if (root != null) {
            inOrderRecursive(root.left);
            System.out.print(root.val + " ");
            inOrderRecursive(root.right);
        }
    }

}
